package Tree;

import com.sun.org.apache.xpath.internal.operations.Bool;

/**
 * @author yyq
 * @create 2021-10-27 13:16
 * 这里我们手动构建二叉树
 * 实现二叉树的前序中序后序遍历
 *
 */
public class BinaryTree {
    public static int count=0;
    public static void main(String[] args) {
        TreeNode root=new TreeNode(1);
        root.left=new TreeNode(2);
        root.right=new TreeNode(3);
        root.left.left=new TreeNode(4);
        root.right.right=new TreeNode(5);
    }

    //前序遍历
    public static void preOrder(TreeNode root){
        System.out.println(root.data);
        if(root.left!=null) preOrder(root.left);
        if(root.right!=null) preOrder(root.right);
    }
    //中序遍历
    public static void inFixOrder(TreeNode root){
        if(root.left!=null) inFixOrder(root.left);
        System.out.println(root.data);
        if(root.right!=null) inFixOrder(root.right);
    }
    //后序遍历
    public static void postOrder(TreeNode root){
        if(root.left!=null) postOrder(root.left);
        if(root.right!=null) postOrder(root.right);
        System.out.println(root.data);
    }

    //前序查找
    public static Employee preFind(Integer id,TreeNode<Employee> root){
        count++;
        if(root.data.getId()==id) {
            System.out.println(count);
            return root.data;
        }
        Employee employee = null;
        if(root.left!=null) {
           employee = preFind(id, root.left);
        }
        if(employee!=null){
            return employee;
        }
        if(root.right!=null) {
           employee = preFind(id, root.right);
        }
        return employee;
    }

    //中序查找
    public static Employee infixFind(Integer id,TreeNode<Employee> root){

        Employee employee=null;
        if(root.left!=null){

             employee= infixFind(id, root.left);
        }
        if(employee!=null){
            return employee;
        }
        count++;
        if(root.data.getId()==id){
            System.out.println(count);
            return root.data;
        }
        if(root.right!=null){
            employee=infixFind(id,root.right);
        }
        return employee;

    }

    //删除节点
    public static   Boolean deleteNode(TreeNode<Integer> root,TreeNode<Integer> parent,Integer fx,int id){
       //找到此节点
        Boolean flag=false;
        if(root.data==id){
            //为叶节点
            if(root.left==null&&root.right==null){
                if(fx==0) {
                    parent.left=null;
                    return true;
                }
                if(fx==1){
                    parent.right=null;
                    return true;
                }

            }
            //为非页节点
            else{
                //如果只有一个右叶子节点时
                if(root.left==null&&root.right!=null){
                    root.data= (Integer) root.right.data;
                    root.right=root.right.right;
                    return true;
                }
                //如果只有一个左叶子节点时
                if(root.left!=null&&root.right==null){
                    root.data= (Integer) root.left.data;
                    root.left=root.left.left;
                    return true;
                }
                //如果有两个节点
                if(root.left!=null&&root.right!=null){
                    TreeNode left=root.left;
                    root.data= (Integer) left.data;
                    root.left=left.left;
                    root.left.right=left.right;
                    return true;
                }
            }
        }
        if(root.left!=null) flag=deleteNode(root.left,root,0,id);
        if(flag) return flag;
        if(root.right!=null) flag=deleteNode(root.right,root,1,id);
        return flag;
    }
}
